package com.yang.Dp;

/**
 * @Author: yang
 * @Description:
 * @Date: Created in 20:19 2022/8/9
 * @Modified By:
 */
public class LeetCode96 {
}
class LeetCode96Solution {
    // 这道题的难点是确定递推公式
    // 具体的还是要再仔细看看代码随想录或者官方解答
    // 个人觉得代码随想录的其实就是详细推导 但是官方笛卡尔积的适合直接记忆做题
    // 结题思路：假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，
    // 当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1
    // 同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2
    // 所以可得G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)

    public int numTrees(int n) {
        // 初始化dp数组
        int[] dp = new int[n + 1];

        // 可以理解为空节点也是一个二叉树
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                // 当前节点数可能的二叉树种数 以xx为节点时的左节点数与右节点数
                // 举例而言，创建以3为根、长度为7的不同二叉搜索树，整个序列是 [1,2,3,4,5,6,7]
                //  我们需要从左子序列[1,2]构建左子树，从右子序列 [4,5,6,7]构建右子树，然后将它们组合就是求笛卡尔积
                // F(3,7)=G(2)⋅G(4) G(7) = F(1,7)+...F(7,7) = G(1)*G(5)+..G(5)G(1)
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
